#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <string>


//数根
//https://www.nowcoder.com/questionTerminal/e2422543519249f292d8435394ab82fe
//int several(int num) {
//    int n = 0;
//    while (num) {
//        n += num % 10;
//        num /= 10;
//    }
//    return n;
//}
//
//int main() {
//    string s;
//    while (cin >> s)
//    {
//        long long roots = 0;
//        int k = 0;
//        for (int i = s.size() - 1; i >= 0; --i)
//        {
//            roots += s[i] - '0';
//        }
//        if (roots < 10)
//        {
//            cout << roots << endl;
//        }
//        else
//        {
//            long long num = several(roots);
//            while (num >= 10) {
//                num = several(num);
//            }
//            cout << num << endl;
//        }
//    }
//    return 0;
//}
//数根优化代码
//int sum(long long num)
//{
//    int ret = 0;
//bk:
//    while (num)
//    {
//        ret += num % 10;
//        num /= 10;
//        if (num == 0 && ret >= 10)
//        {
//            num = ret;
//            ret = 0;
//        }
//    }
//    return ret;
//}
//int main()
//{
//    string s;
//
//    while (cin >> s)
//    {
//        long long num = stoll(s);
//        cout << sum(num) << endl;
//    }
//    return 0;
//}


//星际密码
//https://www.nowcoder.com/questionTerminal/34f17d5f2a8240bea661a23ec095a062
#include <iostream>
using namespace std;

int main()
{
    int n = 0;
    while(cin>>n)
    {
        while(n--)
        {
            int x = 0;
            cin >> x;
            if(x == 0 || x == 1)
            {
                printf("%.4d",1);
            }
            else
            {
                long long arr[2] = {1,1};
                for(int i = 2;i<=x;++i)
                {
                    long long tmp = (arr[0]+arr[1])%10000;
                    arr[0]=arr[1];
                    arr[1]=tmp;
                }
                printf("%.4ld",arr[1]);
            } 
        }
        cout<<endl;
    }
    return 0;
}

